//相交链表
//给你两个单链表的头节点 headA 和 headB ，
//请你找出并返回两个单链表相交的起始节点。
//如果两个链表不存在相交节点，返回 null 。
#include<stdio.h>
#include<stdlib.h>


struct ListNode
{
	int val;
	struct ListNode* next;
};

void SLTNodePrintf(struct ListNode* ps)
{
	struct ListNode* cur = ps;
	while (cur)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}

//思路
//计算A B 的长度 
//让长的先走差距步 asb(lenA-lenB)
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) 
{
	struct ListNode* curA = headA;
	struct ListNode* curB = headB;

	int lenA = 0;
	int lenB = 0;
	while (curA)
	{
		lenA++;
		curA = curA->next;
	}while (curB)
	{
		lenB++;
		curB = curB->next;
	}
	//printf("%d %d", lenA, lenB);  5,6
	int gap = abs(lenA - lenB);
	//printf("%d", gap);  1
	
	//找长的(假设 长的是A)
	struct ListNode* longlist = headA, * shortlist = headB;
	//假设错误
	if (lenA < lenB)
	{
		longlist = headB;
		shortlist = headA;
	}
	//长的先走gap步
	while (gap--)
	{
		longlist = longlist->next;
	}
	//同时走
	while (longlist!=NULL && shortlist!=NULL)
	{
		if (longlist != shortlist)
		{
			longlist = longlist->next;
			shortlist = shortlist->next;
		}
		else
		{
			return longlist;
		}
	}
	return NULL;
}


int main()
{
	struct ListNode* b1 = malloc(sizeof(struct ListNode));
	struct ListNode* b2 = malloc(sizeof(struct ListNode));
	struct ListNode* b3 = malloc(sizeof(struct ListNode));
	//n4相交
	struct ListNode* c1 = malloc(sizeof(struct ListNode));
	struct ListNode* c2 = malloc(sizeof(struct ListNode));
	struct ListNode* c3 = malloc(sizeof(struct ListNode)); 


	struct ListNode* a1 = malloc(sizeof(struct ListNode)); 
	struct ListNode* a2 = malloc(sizeof(struct ListNode)); 



	b1->val = 1;
	b2->val = 1;
	b3->val = 1;

	a1->val = 2;
	a2->val = 2;

	c1->val = 3;
	c2->val = 3;
	c3->val = 3;

	b1->next = b2;
	b2->next = b3;
	b3->next = c1;

	a1->next = a2;
	a2->next = c1;

	c1->next = c2;
	c2->next = c3;
	c3->next = NULL;


	
	SLTNodePrintf(a1);
	SLTNodePrintf(b1);

	struct ListNode* newnode = getIntersectionNode(a1,b1);
	SLTNodePrintf(newnode);

	return 0;
}